#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1005;
int dis[N];
bool vis[N];
void spfa(int s){
	for(int i=0;i<n;i++){
		dis[i]=INF;
	}
	vis[s]=true;
	dis[s]=0;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		vis[cur]=false;
		for(int i=0;i<n;i++){
			if(dis[cur]+g[cur][i]<dis[i]){
				dis[i]=dis[cur]+g[cur][i];
				if(!vis[i]){
					q.push(i);
					vis[i]=true;
				}
			}
		}
	}
}
int main(void){
	return 0;
}
